Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
Про виконання лабораторної роботи № 4
з програмування
Тема: Променевий пошук
Завдання: 58. Усередині піраміди Хеопса є N кімнат, в яких встановлено M пристроїв, кожний з яких складається з двох модулів, що розташовуються в різних кімнатах, і призначені для швидкого переміщення між парою кімнат, у яких встановлені ці модулі. Переміщення відбувається за 2 умовних одиниць часу. У початковий момент часу модулі всіх пристроїв переходять у "підготовчий режим". Кожний з модулів має деякий свій цілочисельний період, під час якого він знаходиться в "підготовчому режимі". Після закінчення цього часу модуль миттєво "спрацьовує", після чого знову переходить у "підготовчий режим". Пристроєм можна скористатися тільки в той момент, коли одночасно "спрацьовують" обидва його модуля. Індіана Джонс зумів проникнути в гробницю фараона. Обстеживши її, він включив пристрої і зібрався йти, але в цей момент прокинувся охоронець гробниці. Тепер Джонсу необхідно якнайшвидше потрапити в кімнату N, у якій знаходиться вихід з піраміди. При цьому з кімнати в кімнату він може попадати тільки за допомогою пристроїв, тому що охоронець, що прокинувся, закрив всі двері у кімнатах піраміди.
Написати програму, що одержує на вході опис розташування пристроїв і їхніх характеристик (періоди часу, через які "спрацьовують" ці модулі), а видає значення оптимального часу і послідовність пристроїв, якими треба скористатися, щоб потрапити з кімнати 1 у кімнату N за цей час.
Програма
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
#include <windows.h>
/****Функція виведення кирилиці****/
void cyrillic(char* text)
{
char* x;
int l,i,size=sizeof(text);
l=strlen(text);
x=(char*)malloc(size);
for(i=0;i<l;i++)
{
x[i]=text[i];
if(x[i]=='і')x[i]='i';
if(x[i]=='І')x[i]='I';
}
x[i]='\0';
CharToOem(x,x);
printf(x);
}
void main()
{
int n,m,i=0,j=0,k,l;
int* x;
cyrillic("\n\tВведіть кількість кімнат з пристроями\n");
scanf("%d",&n);
x=malloc((n*5)*sizeof(int));
for (i=0;i<n;i++)
{
x[i]=rand()%50;
x[i+n]=rand()%50;
x[i+2*n]=rand()%8+3;
while(j<n)
{
j++;
if(x[i]==x[j] && x[i+n]==x[j+n] && i!=j)
{
x[i]=rand()%50;
j=0;
}
}
}
x[1+4*n]=1;//місце знаходження Індіана Джонс
cyrillic("\n\tХарактеристики пристроїв в кімнатах\n");
printf("\n%d,%d -> %d",x[1],x[1+n],x[1+2*n]);
for(i=1;x[0+4*n]!=1;i++)
{
for(j=0;j<n;j++)
{
if(i==1)
{
x[j+3*n]=0;
}
x[j+3*n]++;
if(x[j+3*n]==x[j+2*n])
{
x[j+3*n]=-2;
}
}
for(j=0;j<n;j++)
{
if(x[j+3*n]==-2 && x[j+4*n]==1)
{
k=j+3*n;
for(m=0;m<n;m++)
{
if(x[m+3*n]==-2 && m+3*n!=k)
{
x[m+4*n]=1;x[j+4*n]=0;l=1;
printf("\n%d,%d -> %d",x[m],x[m+n],x[m+2*n]);
break;
}
}
}
if(l==1)
{
l=0;
break;
}
}
}
cyrillic("\n\tЧас за який вибереться Індіана Джонс \n");
printf("\n%d\n",i);l=0;
cyrillic("\n\tКімнати в яких є пристрої позначні 1\n");
for(i=0;i<50;i++)
{
for(j=0;j<50;j++)
{
for(m=0;m<n;m++)
{
if(x[m]==i && x[m+n]==j)
{
printf("1");
l=1;
}
}
if(l==0)
printf("0");
l=0;
}
printf("\n");
}
}
Результат:
Висновок: На дані лабораторні роботі ми навчилися використовувати певні типи даних до різних за типом задач.
